'''
https://leetcode.cn/problems/longest-increasing-subsequence/
'''
import bisect
from typing import List

class Solution:
    # n^2解
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * n    # 以i位置结尾最长递增子序列
        for i in range(1, n):
            for k in range(i):
                if nums[i] > nums[k]:
                    dp[i] = max(dp[i], dp[k] + 1)
        return max(dp)
    # nlogn
    def lengthOfLIS2(self, nums: List[int]) -> int:
        n = len(nums)
        ends = [nums[0]]
        # 在ends 中找 >= num 的最左位置
        def find(num):
            l, r = 0, len(ends) - 1
            res = 0
            while l <= r:
                m = (l + r) // 2
                if ends[m] >= num:
                    res = m
                    r = m - 1
                else:
                    l = m + 1
            return res

        for i in range(1, n):
            k = find(nums[i])
            if nums[i] <= ends[k]:
                ends[k] = nums[i]
            else:
                ends.append(nums[i])
        return len(ends)
    # nlogn
    def lengthOfLIS3(self, nums: List[int]) -> int:
        n = len(nums)
        ends = [nums[0]]
        # nums[i]有效递增位置
        # 当一个nums[i]在ends中查找：
        #       在ends中找 >= nums[i]的最左位置
        #       1) ends[find] == nums[i]    pass
        #       2) nums[i]                  比ends[-1] 都要大的话
        #       1) ends[find] > nums[i]     说明后续的元素，如果想要找到find+1个长度的递增子序列，那么我就是这时候最好的结尾（足够小）
        for i in range(1, n):
            k = bisect.bisect_left(ends, nums[i])
            if k == len(ends):
                ends.append(nums[i])
            else:
                ends[k] = nums[i]
        return len(ends)

    # 最长不递减子序列
    def lengthOfLIS4(self, nums: List[int]) -> int:
        n = len(nums)
        ends = [nums[0]]
        for i in range(1, n):
            k = bisect.bisect_right(ends, nums[i])
            if k == len(ends):  # nums[i] 是最大的
                ends.append(nums[i])
            else:       # ends[k-1] <= nums[i] < ends[k]
                ends[k] = nums[i]
        return len(ends)

nums = [2,3,1,4,2,1,3,5,4,2,5,1]
s = Solution()
print(s.lengthOfLIS3(nums))

arr = [1, 2, 3 , 5]
print(bisect.bisect_left(arr, 4))
print(bisect.bisect_right(arr, 4))
print(bisect.bisect_left(arr, 5))
print(bisect.bisect_right(arr, 5))
print(bisect.bisect_left(arr, 6))
print(bisect.bisect_right(arr, 6))